/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-k-closest-elements
   @Language: C++
   @Datetime: 19-04-05 10:49
   */

class Solution {
public:
	/**
	 * @param A: an integer array
	 * @param target: An integer
	 * @param k: An integer
	 * @return: an integer array
	 */
	vector<int> kClosestNumbers(vector<int> &A, int target, int k) {
		// write your code here
		if(k>A.size()) return A;
		int pos=lower_bound(A.begin(),A.end(),target)-A.begin();
		vector<int> v;
		for(int i=pos-1, j=pos; v.size()<k;){
			if(i>-1 && j<A.size()){
				if(abs(A[i]-target)==abs(A[j]-target)) v.push_back(A[i]<A[j]?A[i--]:A[j++]);
				else v.push_back(abs(A[i]-target)<abs(A[j]-target)?A[i--]:A[j++]);
			}
			else if(i>-1) v.push_back(A[i--]);
			else v.push_back(A[j++]);
		}
		return v;

	}
};
